package org.lql.algo.codecrush.week006;

/**
 * @author: liangqinglong
 * @date: 2025-08-07 17:52
 * @description: 215. 数组中的第K个最大元素 <a href="https://leetcode.cn/problems/kth-largest-element-in-an-array/description/">...</a>
 **/
public class FindKthLargest {


	/**
	 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
	 * <p>
	 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
	 * <p>
	 * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
	 * <p>
	 * <p>
	 * <p>
	 * 示例 1:
	 * <p>
	 * 输入: [3,2,1,5,6,4], k = 2
	 * 输出: 5
	 * 示例 2:
	 * <p>
	 * 输入: [3,2,3,1,2,4,5,5,6], k = 4
	 * 输出: 4
	 * <p>
	 * <p>
	 * 提示：
	 * <p>
	 * 1 <= k <= nums.length <= 105
	 * -104 <= nums[i] <= 104
	 */
	public int findKthLargest(int[] nums, int k) {
		int target = nums.length - k;
		int left = 0, right = nums.length - 1;

		while (left <= right) {
			int pivotIndex = partition(nums, left, right);
			if (pivotIndex == target) {
				return nums[pivotIndex];
			} else if (pivotIndex < target) {
				left = pivotIndex + 1;
			} else {
				right = pivotIndex - 1;
			}
		}
		return -1; // 理论上不会到这
	}

	private int partition(int[] nums, int left, int right) {
		int pivot = nums[right];
		int i = left;
		for (int j = left; j < right; j++) {
			if (nums[j] <= pivot) {
				swap(nums, i, j);
				i++;
			}
		}
		swap(nums, i, right);
		return i;
	}

	private void swap(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}

	public static void main(String[] args) {
		int[] nums = new int[]{3, 2, 1, 5, 6, 4};
		int k = 2;
		FindKthLargest findKthLargest = new FindKthLargest();
		int kthLargest = findKthLargest.findKthLargest(nums, k);
		System.out.println(kthLargest);
	}
}
